1822E - Making Anti-Palindromes - CodeForces Solution

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(true); cin.tie(NULL); cout.tie(NULL)
#define PI 3.141592653589793238462643383279
using namespace std;




void solve()
{
 int n;
 cin>>n;
 string s;
 cin>>s;
 if(n&1)
 {
  cout<<-1<<endl;
  return;
 }
 map<char,int>m;
 for(auto it:s)m[it]++;
 for(int i='a';i<='z';i++)
 {
  if(m[i]>(n/2))
  {
    cout<<-1<<endl;
    return;
  }
 }
 m.clear();
 int count=0;
 for(int i=0;i<n/2;i++)
 {
  if(s[i]==s[n-i-1])
  {
    count++;
    m[s[i]]++;
  }
 }
 for(auto it:m)
 {
  if(it.second*2>count)
  {
    cout<<it.second<<endl;
    return;
  }
 }
 cout<<(count+1)/2<<endl;
}


int main() 
{

fast;
int t;
cin>>t;

// t=1;
while(t--)
{
	solve();
	
}
return 0;
}